/**
 * @param {number[][]} triangle
 * @return {number}
 * 输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
 */
var minimumTotal = function (triangle) {
  const len = triangle.length
  const tree = (arr, index, offset) => {
    if (index === len - 1) {
      return
    }
    index++
    const nextArr = triangle[index]
    arr.forEach((item, i) => {
      item.children = [{ num: nextArr[i + offset] }, { num: nextArr[i + 1 + offset] }]
      tree(item.children, index, i)
    })
  }
  let c = [{ num: triangle[0][0] }]
  tree(c, 0, 0)
  let maxAll = null
  const calc = (arr, max, time, arrs) => {
    if (time === len) {
      if (maxAll === null) {
        maxAll = max
      } else {
        maxAll = Math.min(max, maxAll)
        if (max === -67) {
          console.log(arrs)
        }
      }
      return
    }
    time++
    arr.forEach(item => {
      calc(item.children, max + item.num, time, [...arrs, item.num])
    })
  }
  calc(c, 0, 0, [])
  return maxAll
}
console.log(
  minimumTotal([
    [-7],
    [-2, 1],
    [-5, -5, 9],
    [-4, -5, 4, 4],
    [-6, -6, 2, -1, -5],
    [3, 7, 8, -3, 7, -9],
    [-9, -1, -9, 6, 9, 0, 7],
    [-7, 0, -6, -8, 7, 1, -4, 9],
    [-3, 2, -6, -9, -7, -6, -9, 4, 0],
    [-8, -6, -3, -9, -2, -6, 7, -5, 0, 7],
    [-9, -1, -2, 4, -2, 4, 4, -1, 2, -5, 5],
    [1, 1, -6, 1, -2, -4, 4, -2, 6, -6, 0, 6],
    [-3, -3, -6, -2, -6, -2, 7, -9, -5, -7, -5, 5, 1]
  ])
)
